SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Recursion (computer science)</title>

</head>

Recursion (computer science)

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about recursive approaches to solving problems. For proofs by recursion, see <a href="Mathematical_induction" title="Mathematical induction">Mathematical induction</a>. For recursion in computer science acronyms, see <a href="Recursive_acronym#Computer-related_examples" title="Recursive acronym">Recursive acronym § Computer-related examples</a>. For general use of the term, see <a href="Recursion" title="Recursion">Recursion</a>.</div>

In <a href="Computer_science" title="Computer science">computer science</a>, recursion is a method of solving a <a href="Computational_problem" title="Computational problem">computational problem</a> where the solution depends on solutions to smaller instances of the same problem.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> Recursion solves such <a href="Recursion" title="Recursion">recursive problems</a> by using <a href="Function_(computer_science)" class="mw-redirect" title="Function (computer science)">functions</a> that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.<a href="#cite_note-3">[3]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.</blockquote><div class="templatequotecite">— <a href="Niklaus_Wirth" title="Niklaus Wirth">Niklaus Wirth</a>, Algorithms + Data Structures = Programs, 1976<a href="#cite_note-4">[4]</a></div>

Most computer <a href="Programming_language" title="Programming language">programming languages</a> support recursion by allowing a function to call itself from within its own code. Some <a href="Functional_programming" title="Functional programming">functional programming</a> languages (for instance, <a href="Clojure" title="Clojure">Clojure</a>)<a href="#cite_note-5">[5]</a> do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in <a href="Computability_theory" title="Computability theory">computability theory</a> that these recursive-only languages are <a href="Turing_complete" class="mw-redirect" title="Turing complete">Turing complete</a>; this means that they are as powerful (they can be used to solve the same problems) as <a href="Imperative_language" class="mw-redirect" title="Imperative language">imperative languages</a> based on control structures such as <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">while</code> and <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">for</code>.

Repeatedly calling a function from within itself may cause the <a href="Call_stack" title="Call stack">call stack</a> to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less <a href="Algorithmic_efficiency" title="Algorithmic efficiency">efficient</a>, and, for certain problems, algorithmic or compiler-optimization techniques such as <a href="Tail_call" title="Tail call">tail call</a> optimization may improve computational performance over a naive recursive implementation.

/* start https://en.wikipedia.org/ */

.mw-parser-output .toclimit-2 .toclevel-1 ul,.mw-parser-output .toclimit-3 .toclevel-2 ul,.mw-parser-output .toclimit-4 .toclevel-3 ul,.mw-parser-output .toclimit-5 .toclevel-4 ul,.mw-parser-output .toclimit-6 .toclevel-5 ul,.mw-parser-output .toclimit-7 .toclevel-6 ul{display:none}

/* end https://en.wikipedia.org/ */

</style><div class="toclimit-3"><meta property="mw:PageProp/toc"></div>

<div class="mw-heading mw-heading2"><h2 id="Recursive_functions_and_algorithms">Recursive functions and algorithms</h2></div>

A common <a href="Algorithm_design" class="mw-redirect" title="Algorithm design">algorithm design</a> tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the <a href="Divide-and-conquer_method" class="mw-redirect" title="Divide-and-conquer method">divide-and-conquer method</a>; when combined with a <a href="Lookup_table" title="Lookup table">lookup table</a> that stores the results of previously solved sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> or <a href="Memoization" title="Memoization">memoization</a>.

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result <a href="Trivial_(mathematics)" class="mw-redirect" title="Trivial (mathematics)">trivially</a> (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the <a href="Factorial" title="Factorial">factorial</a> function can be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n(n − 1)!. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".

The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to terminate under normal circumstances—for example, some <a href="Daemon_(computer_software)" class="mw-redirect" title="Daemon (computer software)">system and server processes</a>—are an exception to this.) Neglecting to write a base case, or testing for it incorrectly, can cause an <a href="Infinite_loop" title="Infinite loop">infinite loop</a>.

For some functions (such as one that computes the <a href="Series_(mathematics)" title="Series (mathematics)">series</a> for <a href="E_(mathematical_constant)" title="E (mathematical constant)">e</a> = 1/0! + 1/1! + 1/2! + 1/3! + ...) there is not an obvious base case implied by the input data; for these one may add a <a href="Parameter" title="Parameter">parameter</a> (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by <a href="Corecursion" title="Corecursion">corecursion</a>, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the nth term (nth partial sum)".

<div class="mw-heading mw-heading2"><h2 id="Recursive_data_types">Recursive data types</h2></div>

Many <a href="Computer_program" title="Computer program">computer programs</a> must process or generate an arbitrarily large quantity of <a href="Data" title="Data">data</a>. Recursion is a technique for representing data whose exact size is unknown to the <a href="Programmer" title="Programmer">programmer</a>: the programmer can specify this data with a <a href="Self-referential" class="mw-redirect" title="Self-referential">self-referential</a> definition. There are two types of self-referential definitions: inductive and <a href="Coinductive" class="mw-redirect" title="Coinductive">coinductive</a> definitions.

<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Algebraic_data_type" title="Algebraic data type">Algebraic data type</a></div>

<div class="mw-heading mw-heading3"><h3 id="Inductively_defined_data">Inductively defined data</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Recursive_data_type" title="Recursive data type">Recursive data type</a></div>

An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, <a href="Linked_list" title="Linked list">linked lists</a> can be defined inductively (here, using <a href="Haskell" title="Haskell">Haskell</a> syntax):

<div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre>data ListOfStrings = EmptyList | Cons String ListOfStrings

</pre></div>

The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.

Another example of inductive <a href="Definition" title="Definition">definition</a> is the <a href="Natural_numbers" class="mw-redirect" title="Natural numbers">natural numbers</a> (or positive <a href="Integers" class="mw-redirect" title="Integers">integers</a>):

<pre>A natural number is either 1 or n+1, where n is a natural number.</pre>

Similarly recursive <a href="Definition" title="Definition">definitions</a> are often used to model the structure of <a href="Expression_(programming)" class="mw-redirect" title="Expression (programming)">expressions</a> and <a href="Statement_(programming)" class="mw-redirect" title="Statement (programming)">statements</a> in programming languages. Language designers often express grammars in a syntax such as <a href="Backus%E2%80%93Naur_form" title="Backus–Naur form">Backus–Naur form</a>; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:

| (<expr> * <expr>)

| (<expr> + <expr>)

</pre></div>

This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complicated arithmetic expressions such as <code>(5 * ((3 * 6) + 8))</code>, with more than one product or sum operation in a single expression.

<div class="mw-heading mw-heading3"><h3 id="Coinductively_defined_data_and_corecursion">Coinductively defined data and corecursion</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main articles: <a href="Coinduction" title="Coinduction">Coinduction</a> and <a href="Corecursion" title="Corecursion">Corecursion</a></div>

A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.

A coinductive definition of infinite <a href="Stream_(computer_science)" class="mw-redirect" title="Stream (computer science)">streams</a> of strings, given informally, might look like this:

<pre>A stream of strings is an object s such that:

head(s) is a string, and

tail(s) is a stream of strings.

</pre>

This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the <a href="Accessor" class="mw-redirect" title="Accessor">accessor</a> functions <code>head</code> and <code>tail</code>—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.

Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of <a href="Lazy_evaluation" title="Lazy evaluation">lazy</a> programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n <a href="Prime_numbers" class="mw-redirect" title="Prime numbers">prime numbers</a> is one that can be solved with a corecursive program (e.g. <a href="Fold_(higher-order_function)#Examples" title="Fold (higher-order function)">here</a>).

<div class="mw-heading mw-heading2"><h2 id="Types_of_recursion">Types of recursion</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Single_recursion_and_multiple_recursion">Single recursion and multiple recursion</h3></div>

Recursion that contains only a single self-reference is known as <style data-mw-deduplicate="TemplateStyles:r1238216509">

/* start https://en.wikipedia.org/ */

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}

/* end https://en.wikipedia.org/ */

</style>single recursion, while recursion that contains multiple self-references is known as multiple recursion. Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include <a href="Tree_traversal" title="Tree traversal">tree traversal</a>, such as in a depth-first search.

Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.

Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively entails multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, while tracking two successive values at each step – see <a href="Corecursion#Examples" title="Corecursion">corecursion: examples</a>. A more sophisticated example involves using a <a href="Threaded_binary_tree" title="Threaded binary tree">threaded binary tree</a>, which allows iterative tree traversal, rather than multiple recursion.

<div class="mw-heading mw-heading3"><h3 id="Indirect_recursion">Indirect recursion</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Mutual_recursion" title="Mutual recursion">Mutual recursion</a></div>

Most basic examples of recursion, and most of the examples presented here, demonstrate direct recursion, in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.

Indirect recursion is also called <a href="Mutual_recursion" title="Mutual recursion">mutual recursion</a>, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.

<div class="mw-heading mw-heading3"><h3 id="Anonymous_recursion">Anonymous recursion</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Anonymous_recursion" title="Anonymous recursion">Anonymous recursion</a></div>

Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for <a href="Anonymous_function" title="Anonymous function">anonymous functions</a>, and is known as <a href="Anonymous_recursion" title="Anonymous recursion">anonymous recursion</a>.

<div class="mw-heading mw-heading3"><h3 id="Structural_versus_generative_recursion">Structural versus generative recursion</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Structural_recursion" class="mw-redirect" title="Structural recursion">Structural recursion</a></div>

Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:

<blockquote class="templatequote">[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS.</blockquote><div class="templatequotecite">— Felleisen, Findler, Flatt, and Krishnaurthi, <a href="How_to_Design_Programs" title="How to Design Programs">How to Design Programs</a>, 2001<a href="#cite_note-Felleisen_HtDP_2001-6">[6]</a></div>

Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.

Generative recursion is the alternative:

<blockquote class="templatequote">Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. <a href="How_to_Design_Programs" title="How to Design Programs">HtDP (How to Design Programs)</a> refers to this kind as generative recursion. Examples of generative recursion include: <a href="Euclidean_algorithm" title="Euclidean algorithm">gcd</a>, <a href="Quicksort" title="Quicksort">quicksort</a>, <a href="Binary_search" title="Binary search">binary search</a>, <a href="Mergesort" class="mw-redirect" title="Mergesort">mergesort</a>, <a href="Newton's_method" title="Newton's method">Newton's method</a>, <a href="Fractal" title="Fractal">fractals</a>, and <a href="Adaptive_quadrature" title="Adaptive quadrature">adaptive integration</a>.</blockquote><div class="templatequotecite">— Matthias Felleisen, Advanced Functional Programming, 2002<a href="#cite_note-Felleisen_2002_108-7">[7]</a></div>

This distinction is important in <a href="Termination_analysis#Termination_proof" title="Termination analysis">proving termination</a> of a function.

<ul><li>All structurally recursive functions on finite (<a href="Recursive_data_type" title="Recursive data type">inductively defined</a>) data structures can easily be shown to terminate, via <a href="Structural_induction" title="Structural induction">structural induction</a>: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached.</li>

<li>Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding <a href="Infinite_loops" class="mw-redirect" title="Infinite loops">infinite loops</a> requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is not necessarily guaranteed.</li>

<li>In terms of <a href="Loop_variant" title="Loop variant">loop variants</a>, structural recursion is when there is an obvious loop variant, namely size or complexity, which starts off finite and decreases at each recursive step.</li>

<li>By contrast, generative recursion is when there is not such an obvious loop variant, and termination depends on a function, such as "error of approximation" that does not necessarily decrease to zero, and thus termination is not guaranteed without further analysis.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Implementation_issues">Implementation issues</h2></div>

In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include:

<ul><li>Wrapper function (at top)</li>

<li>Short-circuiting the base case, aka "Arm's-length recursion" (at bottom)</li>

<li>Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough</li></ul>

On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia. Hybrid algorithms are often used for efficiency, to reduce the overhead of recursion in small cases, and arm's-length recursion is a special case of this.

<div class="mw-heading mw-heading3"><h3 id="Wrapper_function">Wrapper function</h3></div>

A <a href="Wrapper_function" title="Wrapper function">wrapper function</a> is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.

Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for <a href="Memoization" title="Memoization">memoization</a>, and handle exceptions and errors. In languages that support <a href="Nested_function" title="Nested function">nested functions</a>, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using <a href="Pass-by-reference" class="mw-redirect" title="Pass-by-reference">pass-by-reference</a>.

<div class="mw-heading mw-heading3"><h3 id="Short-circuiting_the_base_case">Short-circuiting the base case</h3></div>

<caption>Factorial: ordinary vs. short-circuit

</caption>

<th>Ordinary recursion

</th>

<th>Short-circuit recursion

</th></tr>

<tr>

<td valign="TOP"><div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>int fac1(int n) {

if (n <= 0)

return 1;

else

return fac1(n-1)*n;

}

</pre></div>

</td>

<td valign="TOP"><div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>int fac2(int n) {

// assert(n >= 2);

if (n == 2)

return 2;

else

return fac2(n-1)*n;

}

int fac2wrapper(int n) {

return 1;

else

return fac2(n);

}

</pre></div>

</td></tr></tbody></table>

Short-circuiting the base case, also known as arm's-length recursion, consists of checking the base case before making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function. The box shows <a href="C_(programming_language)" title="C (programming language)">C</a> code to shortcut factorial cases 0 and 1.

Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for O(n) algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only O(1) savings.

Conceptually, short-circuiting can be considered to either have the same base case and recursive step, checking the base case only before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading4"><h4 id="Depth-first_search">Depth-first search</h4></div>

A basic example of short-circuiting is given in <a href="Depth-first_search" title="Depth-first search">depth-first search</a> (DFS) of a binary tree; see <a href="#Binary_trees">binary trees</a> section for standard recursive discussion.

The standard recursive algorithm for a DFS is:

<ul><li>base case: If current node is Null, return false</li>

<li>recursive step: otherwise, check value of current node, return true if match, otherwise recurse on children</li></ul>

In short-circuiting, this is instead:

<ul><li>check value of current node, return true if match,</li>

<li>otherwise, on children, if not Null, then recurse.</li></ul>

In terms of the standard steps, this moves the base case check before the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null).

In the case of a <a href="Perfect_binary_tree" class="mw-redirect" title="Perfect binary tree">perfect binary tree</a> of height h, there are 2h+1−1 nodes and 2h+1 Null pointers as children (2 for each of the 2h leaves), so short-circuiting cuts the number of function calls in half in the worst case.

In C, the standard recursive algorithm may be implemented as:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>bool tree_contains(struct node *tree_node, int i) {

if (tree_node == NULL)

return false; // base case

else if (tree_node->data == i)

return true;

else

tree_contains(tree_node->right, i);

}

</pre></div>

The short-circuited algorithm may be implemented as:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>// Wrapper function to handle empty tree

bool tree_contains(struct node *tree_node, int i) {

return false; // empty tree

else

return tree_contains_do(tree_node, i); // call auxiliary function

}

// Assumes tree_node != NULL

bool tree_contains_do(struct node *tree_node, int i) {

if (tree_node->data == i)

return true; // found

else // recurse

return (tree_node->left && tree_contains_do(tree_node->left, i)) ||

(tree_node->right && tree_contains_do(tree_node->right, i));

}

</pre></div>

Note the use of <a href="Short-circuit_evaluation" title="Short-circuit evaluation">short-circuit evaluation</a> of the Boolean && (AND) operators, so that the recursive call is made only if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a Boolean, so the overall expression evaluates to a Boolean. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean || (OR) operator, to only check the right child if the left child fails. In fact, the entire <a href="Control_flow" title="Control flow">control flow</a> of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.

<div class="mw-heading mw-heading3"><h3 id="Hybrid_algorithm">Hybrid algorithm</h3></div>

Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example is <a href="Merge_sort" title="Merge sort">merge sort</a>, which is often implemented by switching to the non-recursive <a href="Insertion_sort" title="Insertion sort">insertion sort</a> when the data is sufficiently small, as in the <a href="Tiled_merge_sort" class="mw-redirect" title="Tiled merge sort">tiled merge sort</a>. Hybrid recursive algorithms can often be further refined, as in <a href="Timsort" title="Timsort">Timsort</a>, derived from a hybrid merge sort/insertion sort.

<div class="mw-heading mw-heading2"><h2 id="Recursion_versus_iteration">Recursion versus iteration</h2></div>

Recursion and <a href="Iteration" title="Iteration">iteration</a> are equally expressive: recursion can be replaced by iteration with an explicit <a href="Call_stack" title="Call stack">call stack</a>, while iteration can be replaced with <a href="Tail_recursion" class="mw-redirect" title="Tail recursion">tail recursion</a>. Which approach is preferable depends on the problem under consideration and the language used. In <a href="Imperative_programming" title="Imperative programming">imperative programming</a>, iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in <a href="Functional_languages" class="mw-redirect" title="Functional languages">functional languages</a> recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable.

Compare the templates to compute xn defined by xn = f(n, xn-1) from xbase:

<table>

<td>

<pre>function recursive(n)

if n == base

return xbase

else

return f(n, recursive(n - 1))

</pre>

</td>

<td>

<pre>function iterative(n)

x = xbase

for i = base + 1 to n

x = f(i, x)

return x

</pre>

</td></tr></tbody></table>

For an imperative language the overhead is to define the function, and for a functional language the overhead is to define the accumulator variable x.

For example, a <a href="Factorial" title="Factorial">factorial</a> function may be implemented iteratively in <a href="C_(programming_language)" title="C (programming language)">C</a> by assigning to a loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>unsigned int factorial(unsigned int n) {

unsigned int product = 1; // empty product is 1

while (n) {

product *= n;

--n;

}

return product;

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Expressive_power">Expressive power</h3></div>

Most <a href="Programming_language" title="Programming language">programming languages</a> in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's <a href="Runtime_environment" class="mw-redirect" title="Runtime environment">runtime environment</a> keeps track of the various <a href="Instance_(computer_science)" title="Instance (computer science)">instances</a> of the function (often using a <a href="Call_stack" title="Call stack">call stack</a>, although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with <a href="Control_flow" title="Control flow">iterative control constructs</a> and simulating the call stack with a <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stack</a> explicitly managed by the program.<a href="#cite_note-9">[9]</a><a href="#cite_note-10">[10]</a>

Conversely, all iterative functions and procedures that can be evaluated by a computer (see <a href="Turing_completeness" title="Turing completeness">Turing completeness</a>) can be expressed in terms of recursive functions; iterative control constructs such as <a href="While_loop" title="While loop">while loops</a> and <a href="For_loop" title="For loop">for loops</a> are routinely rewritten in recursive form in <a href="Functional_language" class="mw-redirect" title="Functional language">functional languages</a>.<a href="#cite_note-11">[11]</a><a href="#cite_note-12">[12]</a> However, in practice this rewriting depends on <a href="Tail_call_elimination" class="mw-redirect" title="Tail call elimination">tail call elimination</a>, which is not a feature of all languages. <a href="C_(programming_language)" title="C (programming language)">C</a>, <a href="Java_(programming_language)" title="Java (programming language)">Java</a>, and <a href="Python_(programming_language)" title="Python (programming language)">Python</a> are notable mainstream languages in which all function calls, including <a href="Tail_call" title="Tail call">tail calls</a>, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form may <a href="Stack_overflow" title="Stack overflow">overflow the call stack</a>, although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities.

<div class="mw-heading mw-heading3"><h3 id="Performance_issues">Performance issues</h3></div>

In languages (such as <a href="C_(programming_language)" title="C (programming language)">C</a> and <a href="Java_(programming_language)" title="Java (programming language)">Java</a>) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in <a href="Functional_languages" class="mw-redirect" title="Functional languages">functional languages</a>, a function call (particularly a <a href="Tail_call" title="Tail call">tail call</a>) is typically a very fast operation, and the difference is usually less noticeable.

As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the <a href="Compiler" title="Compiler">compiler</a> used. In languages where looping constructs are preferred, the iterative version may be as much as several <a href="Orders_of_magnitude" class="mw-redirect" title="Orders of magnitude">orders of magnitude</a> faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration.

<div class="mw-heading mw-heading3"><h3 id="Stack_space">Stack space</h3></div>

In some programming languages, the maximum size of the <a href="Call_stack" title="Call stack">call stack</a> is much less than the space available in the <a href="Heap_(programming)" class="mw-redirect" title="Heap (programming)">heap</a>, and recursive algorithms tend to require more stack space than iterative algorithms. Consequently, these languages sometimes place a limit on the depth of recursion to avoid <a href="Stack_buffer_overflow" title="Stack buffer overflow">stack overflows</a>; <a href="Python_(programming_language)" title="Python (programming language)">Python</a> is one such language.<a href="#cite_note-13">[13]</a> Note the caveat below regarding the special case of <a href="Tail_recursion" class="mw-redirect" title="Tail recursion">tail recursion</a>.

<div class="mw-heading mw-heading3"><h3 id="Vulnerability">Vulnerability</h3></div>

Because recursive algorithms can be subject to stack overflows, they may be vulnerable to <a href="Pathological_(mathematics)" title="Pathological (mathematics)">pathological</a> or <a href="Malware" title="Malware">malicious</a> input.<a href="#cite_note-14">[14]</a> Some malware specifically targets a program's call stack and takes advantage of the stack's inherently recursive nature.<a href="#cite_note-15">[15]</a> Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, and <a href="Exception_handling" title="Exception handling">exception handling</a> <a href="Logic" title="Logic">logic</a> may not prevent the corresponding <a href="Process_(computing)" title="Process (computing)">process</a> from being <a href="Process_state#Terminated" title="Process state">terminated</a>.<a href="#cite_note-16">[16]</a>

<div class="mw-heading mw-heading3"><h3 id="Multiply_recursive_problems">Multiply recursive problems</h3></div>

Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is <a href="Tree_traversal" title="Tree traversal">tree traversal</a> as in <a href="Depth-first_search" title="Depth-first search">depth-first search</a>; though both recursive and iterative methods are used,<a href="#cite_note-17">[17]</a> they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples include <a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">divide-and-conquer algorithms</a> such as <a href="Quicksort" title="Quicksort">Quicksort</a>, and functions such as the <a href="Ackermann_function" title="Ackermann function">Ackermann function</a>. All of these algorithms can be implemented iteratively with the help of an explicit <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stack</a>, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution.

<div class="mw-heading mw-heading3"><h3 id="Refactoring_recursion">Refactoring recursion</h3></div>

Recursive algorithms can be replaced with non-recursive counterparts.<a href="#cite_note-18">[18]</a> One method for replacing recursive algorithms is to simulate them using <a href="Memory_management" title="Memory management">heap memory</a> in place of <a href="Stack_memory" class="mw-redirect" title="Stack memory">stack memory</a>.<a href="#cite_note-19">[19]</a> An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging.<a href="#cite_note-20">[20]</a> For example, recursive algorithms for <a href="Matching_wildcards" title="Matching wildcards">matching wildcards</a>, such as <a href="Rich_Salz" class="mw-redirect" title="Rich Salz">Rich Salz</a>' <a href="Wildmat" title="Wildmat">wildmat</a> algorithm,<a href="#cite_note-21">[21]</a> were once typical. Non-recursive algorithms for the same purpose, such as the <a href="Krauss_matching_wildcards_algorithm" class="mw-redirect" title="Krauss matching wildcards algorithm">Krauss matching wildcards algorithm</a>, have been developed to avoid the drawbacks of recursion<a href="#cite_note-22">[22]</a> and have improved only gradually based on techniques such as collecting <a href="Software_testing" title="Software testing">tests</a> and <a href="Profiling_(computer_programming)" title="Profiling (computer programming)">profiling</a> performance.<a href="#cite_note-23">[23]</a>

<div class="mw-heading mw-heading2"><h2 id="Tail-recursive_functions">Tail-recursive functions</h2></div>

Tail-recursive functions are functions in which all recursive calls are <a href="Tail_call" title="Tail call">tail calls</a> and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is not tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a <a href="Compiler" title="Compiler">compiler</a> or <a href="Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> that treats tail-recursive calls as <a href="Goto" title="Goto">jumps</a> rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.

<th><a href="Tail_recursion" class="mw-redirect" title="Tail recursion">Tail recursion</a>:

</th>

<th>Augmenting recursion:

</th></tr>

<tr>

<td><div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>//INPUT: Integers x, y such that x >= y and y >= 0

int gcd(int x, int y)

{

if (y == 0)

return x;

else

return gcd(y, x % y);

}

</pre></div>

</td>

<td><div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>//INPUT: n is an Integer such that n >= 0

int fact(int n)

{

if (n == 0)

return 1;

else

return n * fact(n - 1);

}

</pre></div>

</td></tr></tbody></table>

The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the <a href="Call_stack" title="Call stack">call stack</a>; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.

<div class="mw-heading mw-heading2"><h2 id="Order_of_execution">Order of execution</h2></div>

Consider these two functions:

<div class="mw-heading mw-heading3"><h3 id="Function_1">Function 1</h3></div>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>void recursiveFunction(int num) {

printf("%d\n", num);

if (num < 4)

recursiveFunction(num + 1);

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Function_2">Function 2</h3></div>

}

</pre></div>

The output of function 2 is that of function 1 with the lines swapped.

In the case of a function calling itself only once, instructions placed before the recursive call are executed once per recursion before any of the instructions placed after the recursive call. The latter are executed repeatedly after the maximum recursion has been reached.

Also note that the order of the print statements is reversed, which is due to the way the functions and statements are stored on the <a href="Call_stack" title="Call stack">call stack</a>.

<div class="mw-heading mw-heading2"><h2 id="Recursive_procedures">Recursive procedures</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Factorial">Factorial</h3></div>

A classic example of a recursive procedure is the function used to calculate the <a href="Factorial" title="Factorial">factorial</a> of a <a href="Natural_number" title="Natural number">natural number</a>:

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}</annotation>

</semantics>

</math><img src="./fbc0a05bb5402570afdac251df1661194639d397.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:36.618ex; height:6.176ex;" alt="{\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}" loading="lazy"></dd></dl>

<th><a href="Pseudocode" title="Pseudocode">Pseudocode</a> (recursive):

</th></tr>

<tr>

<td>

<pre>function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × ... × 1]

1. if n is 0, return 1

2. otherwise, return [ n × factorial(n-1) ]

end factorial

</pre>

</td></tr></tbody></table>

The function can also be written as a <a href="Recurrence_relation" title="Recurrence relation">recurrence relation</a>:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{n}=nb_{n-1}}</annotation>

</semantics>

</math><img src="./2e489a1211cc945f05a486d09506fdb827febc23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.026ex; height:2.509ex;" alt="{\displaystyle b_{n}=nb_{n-1}}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{0}=1}</annotation>

</semantics>

</math><img src="./6e891f2e26ca623a2f9bbd0bfef87a4dfac0a20f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.313ex; height:2.509ex;" alt="{\displaystyle b_{0}=1}" loading="lazy"></dd></dl>

This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:

<th>Computing the recurrence relation for n = 4:

</th></tr>

<tr>

<td>

<pre>b4 = 4 × b3

= 4 × (3 × b2)

= 4 × (3 × (2 × b1))

= 4 × (3 × (2 × (1 × b0)))

= 4 × (3 × (2 × (1 × 1)))

= 4 × (3 × (2 × 1))

= 4 × (3 × 2)

= 4 × 6

= 24

</pre>

</td></tr></tbody></table>

This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:

<th>Pseudocode (iterative):

</th></tr>

<tr>

<td>

<pre>function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × ... × 1]

1. create new variable called running_total with a value of 1

2. begin loop

1. if n is 0, exit loop

2. set running_total to (running_total × n)

3. decrement n

4. repeat loop

3. return running_total

end factorial

</pre>

</td></tr></tbody></table>

The imperative code above is equivalent to this mathematical definition using an accumulator variable <var>t</var>:

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}}">

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}}</annotation>

</semantics>

</math><img src="./5425ae0a78b654f37c41e3e6acfd0b2e59c61b5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:44.773ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}}" loading="lazy"></dd></dl>

The definition above translates straightforwardly to <a href="Functional_programming_language" class="mw-redirect" title="Functional programming language">functional programming languages</a> such as <a href="Scheme_(programming_language)" title="Scheme (programming language)">Scheme</a>; this is an example of iteration implemented recursively.

<div class="mw-heading mw-heading3"><h3 id="Greatest_common_divisor">Greatest common divisor</h3></div>

The <a href="Euclidean_algorithm" title="Euclidean algorithm">Euclidean algorithm</a>, which computes the <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> of two integers, can be written recursively.

Function definition:

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mi>remainder</mi>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}}</annotation>

</semantics>

</math><img src="./66b3eae7c177b5a9738c42383c664048d8f239a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:47.12ex; height:6.176ex;" alt="{\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}}" loading="lazy"></dd></dl>

<th><a href="Pseudocode" title="Pseudocode">Pseudocode</a> (recursive):

</th></tr>

<tr>

<td>

<pre>function gcd is:

input: integer x, integer y such that x > 0 and y >= 0

1. if y is 0, return x

2. otherwise, return [ gcd( y, (remainder of x/y) ) ]

end gcd

</pre>

</td></tr></tbody></table>

<a href="Recurrence_relation" title="Recurrence relation">Recurrence relation</a> for greatest common divisor, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\%y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\%y}</annotation>

</semantics>

</math><img src="./f1b133f8669e2ad9a88369d2e490d6efb60956dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.421ex; height:2.676ex;" alt="{\displaystyle x\%y}" loading="lazy"> expresses the <a href="Remainder" title="Remainder">remainder</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x/y}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x/y}</annotation>

</semantics>

</math><img src="./c9f79732fa39115855a4cf9b64d2a63971a41046.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.648ex; height:2.843ex;" alt="{\displaystyle x/y}" loading="lazy">:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(x,y)=\gcd(y,x\%y)}</annotation>

</semantics>

</math><img src="./c1fe0cd9431d08127f9c1110d4b973207e186ff1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.821ex; height:2.843ex;" alt="{\displaystyle \gcd(x,y)=\gcd(y,x\%y)}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\neq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\neq 0}</annotation>

</semantics>

</math><img src="./fe09d44abefff1fcada712301b088a303591f9e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.416ex; height:2.676ex;" alt="{\displaystyle y\neq 0}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(x,0)=x}</annotation>

</semantics>

</math><img src="./49261e66420afa094166cac921c0195727307eca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.251ex; height:2.843ex;" alt="{\displaystyle \gcd(x,0)=x}" loading="lazy"></dd></dl>

<th>Computing the recurrence relation for x = 27 and y = 9:

</th></tr>

<tr>

<td>

<pre>gcd(27, 9) = gcd(9, 27 % 9)

= gcd(9, 0)

= 9

</pre>

</td></tr>

<tr>

<th>Computing the recurrence relation for x = 111 and y = 259:

</th></tr>

<tr>

<td>

<pre>gcd(111, 259) = gcd(259, 111 % 259)

= gcd(259, 111)

= gcd(111, 259 % 111)

= gcd(111, 37)

= gcd(37, 111 % 37)

= gcd(37, 0)

= 37

</pre>

</td></tr></tbody></table>

The recursive program above is <a href="Tail-recursive" class="mw-redirect" title="Tail-recursive">tail-recursive</a>; it is equivalent to an iterative algorithm, and the computation shown above shows the steps of evaluation that would be performed by a language that eliminates tail calls. Below is a version of the same algorithm using explicit iteration, suitable for a language that does not eliminate tail calls. By maintaining its state entirely in the variables x and y and using a looping construct, the program avoids making recursive calls and growing the call stack.

<th>Pseudocode (iterative):

</th></tr>

<tr>

<td>

<pre>function gcd is:

input: integer x, integer y such that x >= y and y >= 0

1. create new variable called remainder

2. begin loop

1. if y is zero, exit loop

2. set remainder to the remainder of x/y

3. set x to y

4. set y to remainder

5. repeat loop

3. return x

end gcd

</pre>

</td></tr></tbody></table>

The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.

<div class="mw-heading mw-heading3"><h3 id="Towers_of_Hanoi">Towers of Hanoi</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Towers_of_Hanoi" class="mw-redirect" title="Towers of Hanoi">Towers of Hanoi</a></div>

The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion.<a href="#cite_note-24">[24]</a><a href="#cite_note-25">[25]</a> There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with n disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?

Function definition:

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}}">

<mi>hanoi</mi>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mi>hanoi</mi>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}}</annotation>

</semantics>

</math><img src="./52078a04ec62c4a55887e2cd9011acb238c34452.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:43.879ex; height:6.176ex;" alt="{\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}}" loading="lazy"></dd></dl>

Recurrence relation for hanoi:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{n}=2h_{n-1}+1}</annotation>

</semantics>

</math><img src="./ef787d90c11406d902ea1602275c1aa3f7562a15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.479ex; height:2.509ex;" alt="{\displaystyle h_{n}=2h_{n-1}+1}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{1}=1}</annotation>

</semantics>

</math><img src="./083d0eaf2fe9466f7e1ec69edf7f202b8c0b8851.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.654ex; height:2.509ex;" alt="{\displaystyle h_{1}=1}" loading="lazy"></dd></dl>

<th>Computing the recurrence relation for n = 4:

</th></tr>

<tr>

<td>

<pre>hanoi(4) = 2×hanoi(3) + 1

= 2×(2×hanoi(2) + 1) + 1

= 2×(2×(2×hanoi(1) + 1) + 1) + 1

= 2×(2×(2×1 + 1) + 1) + 1

= 2×(2×(3) + 1) + 1

= 2×(7) + 1

= 15

</pre>

</td></tr></tbody></table>

Example implementations:

<th><a href="Pseudocode" title="Pseudocode">Pseudocode</a> (recursive):

</th></tr>

<tr>

<td>

<pre>function hanoi is:

input: integer n, such that n >= 1

1. if n is 1 then return 1

2. return [2 * [call hanoi(n-1)] + 1]

end hanoi

</pre>

</td></tr></tbody></table>

Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.<a href="#cite_note-26">[26]</a>

<th>An explicit formula for Towers of Hanoi:

</th></tr>

<tr>

<td>

<pre>h1 = 1 = 21 - 1

h2 = 3 = 22 - 1

h3 = 7 = 23 - 1

h4 = 15 = 24 - 1

h5 = 31 = 25 - 1

h6 = 63 = 26 - 1

h7 = 127 = 27 - 1

</pre>

<pre>In general:

hn = 2n - 1, for all n >= 1

</pre>

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Binary_search">Binary search</h3></div>

The <a href="Binary_search" title="Binary search">binary search</a> algorithm is a method of searching a <a href="Sorted_array" title="Sorted array">sorted array</a> for a single element by cutting the array in half with each recursive pass. The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new (and smaller) array. Typically the array's size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.

Example implementation of binary search in C:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> /*

Call binary_search with proper initial conditions.

INPUT:

data is an array of integers SORTED in ASCENDING order,

toFind is the integer to search for,

count is the total number of elements in the array

OUTPUT:

result of binary_search

*/

int search(int *data, int toFind, int count)

{

// Start = 0 (beginning index)

// End = count - 1 (top index)

return binary_search(data, toFind, 0, count-1);

}

/*

Binary Search Algorithm.

INPUT:

data is a array of integers SORTED in ASCENDING order,

toFind is the integer to search for,

start is the minimum array index,

end is the maximum array index

OUTPUT:

position of the integer toFind within array data,

-1 if not found

*/

int binary_search(int *data, int toFind, int start, int end)

{

//Get the midpoint.

int mid = start + (end - start)/2; //Integer division

if (start > end) //Stop condition (base case)

return -1;

else if (data[mid] == toFind) //Found, return index

return mid;

else if (data[mid] > toFind) //Data is greater than toFind, search lower half

return binary_search(data, toFind, start, mid-1);

else //Data is less than toFind, search upper half

return binary_search(data, toFind, mid+1, end);

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Recursive_data_structures_(structural_recursion)">Recursive data structures (structural recursion)</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Recursive_data_type" title="Recursive data type">Recursive data type</a></div>

An important application of recursion in computer science is in defining dynamic data structures such as <a href="List_(abstract_data_type)" title="List (abstract data type)">lists</a> and <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">trees</a>. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array must be set at compile time.

"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."<a href="#cite_note-27">[27]</a>

</blockquote>

The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively.

As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.<a href="#cite_note-Felleisen_2002_108-7">[7]</a>

</blockquote>

<div class="mw-heading mw-heading3"><h3 id="Linked_lists">Linked lists</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Linked_list" title="Linked list">Linked list</a></div>

Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element of struct node is a pointer to another struct node, effectively creating a list type.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>struct node

{

int data; // some integer data

struct node *next; // pointer to another struct node

};

</pre></div>

Because the struct node data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The list_print procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the list_print procedure.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>void list_print(struct node *list)

{

if (list != NULL) // base case

{

printf ("%d ", list->data); // print integer data followed by a space

list_print (list->next); // recursive call on the next node

}

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Binary_trees">Binary trees</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Binary_tree" title="Binary tree">Binary tree</a></div>

Below is a simple definition for a binary tree node. Like the node for linked lists, it is defined in terms of itself, recursively. There are two self-referential pointers: left (pointing to the left sub-tree) and right (pointing to the right sub-tree).

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>struct node

{

int data; // some integer data

struct node *left; // pointer to the left subtree

struct node *right; // point to the right subtree

};

</pre></div>

Operations on the tree can be implemented using recursion. Note that because there are two self-referencing pointers (left and right), tree operations may require two recursive calls:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>// Test if tree_node contains i; return 1 if so, 0 if not.

int tree_contains(struct node *tree_node, int i) {

return 0; // base case

return 1;

else

return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);

}

</pre></div>

At most two recursive calls will be made for any given call to tree_contains as defined above.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>// Inorder traversal:

void tree_print(struct node *tree_node) {

if (tree_node != NULL) { // base case

tree_print(tree_node->left); // go left

printf("%d ", tree_node->data); // print the integer followed by a space

tree_print(tree_node->right); // go right

}

}

</pre></div>

The above example illustrates an <a href="Tree_traversal" title="Tree traversal">in-order traversal</a> of the binary tree. A <a href="Binary_search_tree" title="Binary search tree">Binary search tree</a> is a special case of the binary tree where the data elements of each node are in order.

<div class="mw-heading mw-heading3"><h3 id="Filesystem_traversal">Filesystem traversal</h3></div>

Since the number of files in a <a href="Filesystem" class="mw-redirect" title="Filesystem">filesystem</a> may vary, <a href="Recursion" title="Recursion">recursion</a> is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of <a href="Tree_traversal" title="Tree traversal">tree traversal</a>, therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a <a href="Preorder_traversal" class="mw-redirect" title="Preorder traversal">preorder traversal</a> of a filesystem.

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr mw-highlight-lines" dir="ltr"><pre>import java.io.File;

public class FileSystem {

public static void main(String [] args) {

traverse();

}

/**

* Obtains the filesystem roots

* Proceeds with the recursive filesystem traversal

*/

private static void traverse() {

File[] fs = File.listRoots();

for (int i = 0; i < fs.length; i++) {

System.out.println(fs[i]);

if (fs[i].isDirectory() && fs[i].canRead()) {

rtraverse(fs[i]);

}

/**

* Recursively traverse a given directory

*

* @param fd indicates the starting point of traversal

*/

private static void rtraverse(File fd) {

File[] fss = fd.listFiles();

for (int i = 0; i < fss.length; i++) {

System.out.println(fss[i]);

if (fss[i].isDirectory() && fss[i].canRead()) {

rtraverse(fss[i]);

}

}

</pre></div>

This code is both recursion and <a href="Iteration" title="Iteration">iteration</a> - the files and directories are iterated, and each directory is opened recursively.

The "rtraverse" method is an example of direct recursion, whilst the "traverse" method is a wrapper function.

The "base case" scenario is that there will always be a fixed number of files and/or directories in a given filesystem.

<div class="mw-heading mw-heading2"><h2 id="Time-efficiency_of_recursive_algorithms">Time-efficiency of recursive algorithms</h2></div>

The <a href="Time_complexity" title="Time complexity">time efficiency</a> of recursive algorithms can be expressed in a <a href="Recurrence_relation" title="Recurrence relation">recurrence relation</a> of <a href="Big_O_notation" title="Big O notation">Big O notation</a>. They can (usually) then be simplified into a single Big-O term.

<div class="mw-heading mw-heading3"><h3 id="Shortcut_rule_(master_theorem)">Shortcut rule (master theorem)</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Master_theorem_(analysis_of_algorithms)" title="Master theorem (analysis of algorithms)">Master theorem (analysis of algorithms)</a></div>

If the time-complexity of the function is in the form

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=a\cdot T(n/b)+f(n)}</annotation>

</semantics>

</math>

Then the Big O of the time-complexity is thus:

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=O(n^{\log _{b}a-\varepsilon })}</annotation>

</semantics>

</math><img src="./beb3fb687fc8d3f21479f93c3fc406712c588f3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.93ex; height:3.176ex;" alt="{\displaystyle f(n)=O(n^{\log _{b}a-\varepsilon })}" loading="lazy"> for some constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=\Theta (n^{\log _{b}a})}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=\Theta (n^{\log _{b}a})}</annotation>

</semantics>

</math><img src="./34ce8e979e6eada403e7044342c39fdf41815f22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.278ex; height:3.176ex;" alt="{\displaystyle T(n)=\Theta (n^{\log _{b}a})}" loading="lazy"></li>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=\Theta (n^{\log _{b}a})}</annotation>

</semantics>

</math><img src="./eee762297fbff4f695d84fd6eb3a9ea87b5647c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.92ex; height:3.176ex;" alt="{\displaystyle f(n)=\Theta (n^{\log _{b}a})}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}</annotation>

</semantics>

</math><img src="./b30978415211771d1d567ce2ff24228c73e58271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.419ex; height:3.176ex;" alt="{\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}" loading="lazy"></li>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=\Omega (n^{\log _{b}a+\varepsilon })}</annotation>

</semantics>

</math><img src="./ffc4a9b70dcc15fdb9942fa09d2d04a833b34204.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.835ex; height:3.176ex;" alt="{\displaystyle f(n)=\Omega (n^{\log _{b}a+\varepsilon })}" loading="lazy"> for some constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy">, and if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}</annotation>

</semantics>

</math><img src="./d5876b27e26e38632de6c5ea675420b643517437.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.819ex; height:2.843ex;" alt="{\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}" loading="lazy"> for some constant c < 1 and all sufficiently large n, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=\Theta (f(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=\Theta (f(n))}</annotation>

</semantics>

</math><img src="./e3f2ea15b66701b4ed7351155df63020b3ad5dc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.039ex; height:2.843ex;" alt="{\displaystyle T(n)=\Theta (f(n))}" loading="lazy"></li></ul>

where a represents the number of recursive calls at each level of recursion, b represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and f(n) represents the work that the function does independently of any recursion (e.g. partitioning, recombining) at each level of recursion.

<div class="mw-heading mw-heading2"><h2 id="Recursion_in_Logic_Programming">Recursion in Logic Programming</h2></div>

In the procedural interpretation of <a href="Logic_programming" title="Logic programming">logic programs</a>, clauses (or rules) of the form <code class="mw-highlight mw-highlight-lang-prolog mw-content-ltr" dir="ltr">A :- B</code> are treated as procedures, which reduce goals of the form <code>A</code> to subgoals of the form <code>B</code>.

For example, the <a href="Prolog" title="Prolog">Prolog</a> clauses:

<div class="mw-highlight mw-highlight-lang-prolog mw-content-ltr" dir="ltr"><pre>path(X,Y) :- arc(X,Y).

path(X,Y) :- arc(X,Z), path(Z,Y).

</pre></div>

define a procedure, which can be used to search for a path from X to Y, either by finding a direct arc from X to Y, or by finding an arc from X to Z, and then searching recursively for a path from Z to Y. Prolog executes the procedure by reasoning top-down (or <a href="Backward_chaining" title="Backward chaining">backwards</a>) and searching the space of possible paths depth-first, one branch at a time. If it tries the second clause, and finitely fails to find a path from Z to Y, it backtracks and tries to find an arc from X to another node, and then searches for a path from that other node to Y.

However, in the logical reading of logic programs, clauses are understood <a href="Declarative_program" class="mw-redirect" title="Declarative program">declaratively</a> as universally quantified conditionals. For example, the recursive clause of the path-finding procedure is understood as <a href="Knowledge_representation_and_reasoning" title="Knowledge representation and reasoning">representing the knowledge</a> that, for every X, Y and Z, if there is an arc from X to Z and a path from Z to Y then there is a path from X to Y. In symbolic form:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall X,Y,Z(arc(X,Z)\land path(Z,Y)\rightarrow path(X,Y)).}</annotation>

</semantics>

</math><img src="./a5d7004a9fae850a949eed90114ec03a2f3c0366.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.285ex; height:2.843ex;" alt="{\displaystyle \forall X,Y,Z(arc(X,Z)\land path(Z,Y)\rightarrow path(X,Y)).}" loading="lazy"></dd></dl>

The logical reading frees the reader from needing to know how the clause is used to solve problems. The clause can be used top-down, as in Prolog, to reduce problems to subproblems. Or it can be used bottom-up (or <a href="Forward_chaining" title="Forward chaining">forwards</a>), as in <a href="Datalog" title="Datalog">Datalog</a>, to derive conclusions from conditions. This <a href="Separation_of_concerns" title="Separation of concerns">separation of concerns</a> is a form of <a href="Abstraction_(computer_science)" title="Abstraction (computer science)">abstraction</a>, which separates declarative knowledge from problem solving methods (see <a href="Algorithm#Algorithm_=_Logic_+_Control" title="Algorithm">Algorithm#Algorithm = Logic + Control</a>).<a href="#cite_note-28">[28]</a>

<div class="mw-heading mw-heading2"><h2 id="Infinite_recursion">Infinite recursion</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Infinite_loop#Infinite_recursion" title="Infinite loop">Infinite loop § Infinite recursion</a></div>

A common mistake among programmers is not providing a way to exit a recursive function, often by omitting or incorrectly checking the base case, letting it run (at least theoretically) infinitely by endlessly calling itself recursively. This is called infinite recursion, and the program will never terminate. In practice, this typically exhausts the available <a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">stack</a> space. In most programming environments, a program with infinite recursion will not really run forever. Eventually, something will break and the program will report an error.<a href="#cite_note-29">[29]</a>

Below is a Java code that would use infinite recursion:<div class="mw-highlight mw-highlight-lang-java mw-content-ltr mw-highlight-lines" dir="ltr"><pre>public class InfiniteRecursion {

static void recursive() { // Recursive Function with no way out

recursive();

}

public static void main(String[] args) {

recursive(); // Executes the recursive function upon runtime

}

}

</pre></div>

Running this code will result in a <a href="Stack_overflow" title="Stack overflow">stack overflow</a> error.

<ul><li><a href="Functional_programming" title="Functional programming">Functional programming</a></li>

<li><a href="Computational_problem" title="Computational problem">Computational problem</a></li>

<li><a href="Hierarchical_and_recursive_queries_in_SQL" title="Hierarchical and recursive queries in SQL">Hierarchical and recursive queries in SQL</a></li>

<li><a href="Kleene%E2%80%93Rosser_paradox" title="Kleene–Rosser paradox">Kleene–Rosser paradox</a></li>

<li><a href="Open_recursion" class="mw-redirect" title="Open recursion">Open recursion</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a> (in general)</li>

<li><a href="Sierpi%C5%84ski_curve" title="Sierpiński curve">Sierpiński curve</a></li>

<li><a href="McCarthy_91_function" title="McCarthy 91 function">McCarthy 91 function</a></li>

<li><a href="%CE%9C-recursive_function" class="mw-redirect" title="Μ-recursive function">μ-recursive functions</a></li>

<li><a href="Primitive_recursive_function" title="Primitive recursive function">Primitive recursive functions</a></li>

<li><a href="Tak_(function)" title="Tak (function)">Tak (function)</a></li>

<li><a href="Logic_programming" title="Logic programming">Logic programming</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGrahamKnuthPatashnik1990" class="citation book cs1">Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). <a rel="nofollow" class="external text" href="http://www-cs-faculty.stanford.edu/~knuth/gkp.html">"1: Recurrent Problems"</a>. Concrete Mathematics. Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-55802-5</bdi>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKuhailNegreirosSeffah2021" class="citation journal cs1">Kuhail, M. A.; Negreiros, J.; Seffah, A. (2021). <a rel="nofollow" class="external text" href="http://www.wiete.com.au/journals/WTE&TE/Pages/Vol.19,%20No.%202%20(2021)/03-Kuhail-M.pdf">"Teaching Recursive Thinking using Unplugged Activities"</a> (PDF). World Transactions on Engineering and Technology Education. 19: 169–175.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFEpp1995" class="citation book cs1">Epp, Susanna (1995). <a rel="nofollow" class="external text" href="https://archive.org/details/discretemathema000epps/page/427">Discrete Mathematics with Applications</a> (2nd ed.). PWS Publishing Company. p. <a rel="nofollow" class="external text" href="https://archive.org/details/discretemathema000epps/page/427">427</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-53494446-9</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFWirth1976" class="citation book cs1"><a href="Niklaus_Wirth" title="Niklaus Wirth">Wirth, Niklaus</a> (1976). <a rel="nofollow" class="external text" href="https://archive.org/details/algorithmsdatast00wirt/page/126">Algorithms + Data Structures = Programs</a>. <a href="Prentice-Hall" class="mw-redirect" title="Prentice-Hall">Prentice-Hall</a>. p. <a rel="nofollow" class="external text" href="https://archive.org/details/algorithmsdatast00wirt/page/126">126</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13022418-7</bdi>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while">"Functional Programming | Clojure for the Brave and True"</a>. www.braveclojure.com. Retrieved 2020-10-21.</cite>

</li>

<li id="cite_note-Felleisen_HtDP_2001-6"><a href="#cite_ref-Felleisen_HtDP_2001_6-0">^</a> <a href="#CITEREFFelleisenFindlerFlattKrishnamurthi2001">Felleisen et al. 2001</a>, <a rel="nofollow" class="external text" href="http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html">art V "Generative Recursion</a>

</li>

<li id="cite_note-Felleisen_2002_108-7">^ <a href="#cite_ref-Felleisen_2002_108_7-0">a</a> <a href="#cite_ref-Felleisen_2002_108_7-1">b</a> <cite id="CITEREFFelleisen2002" class="citation book cs1">Felleisen, Matthias (2002). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Y3GqCAAAQBAJ&pg=PA108">"Developing Interactive Web Programs"</a>. In Jeuring, Johan (ed.). <a rel="nofollow" class="external text" href="ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Advanced%20Functional%20Programming%204%20conf.,%20AFP%202002%20(LNCS2638,%20Springer,%202003)(ISBN%203540401326)(O)(222s).pdf#page=109">Advanced Functional Programming: 4th International School</a> (PDF). Springer. p. 108. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540448334</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFMonganGiguèreKindler2013" class="citation book cs1">Mongan, John; Giguère, Eric; Kindler, Noah (2013). <a rel="nofollow" class="external text" href="https://archive.org/details/programminginter00mong_658">Programming Interviews Exposed: Secrets to Landing Your Next Job</a> (3rd ed.). <a href="Wiley_(publisher)" title="Wiley (publisher)">Wiley</a>. p. <a rel="nofollow" class="external text" href="https://archive.org/details/programminginter00mong_658/page/n148">115</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-118-26136-1</bdi>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFHetland2010" class="citation cs2">Hetland, Magnus Lie (2010), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=4cytGpIPYsAC&pg=PA79">Python Algorithms: Mastering Basic Algorithms in the Python Language</a>, Apress, p. 79, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781430232384</bdi></cite>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFDrozdek2012" class="citation cs2">Drozdek, Adam (2012), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=PRgLAAAAQBAJ&pg=PA197">Data Structures and Algorithms in C++</a> (4th ed.), Cengage Learning, p. 197, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781285415017</bdi></cite>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFShivers" class="citation web cs1">Shivers, Olin. <a rel="nofollow" class="external text" href="http://www.ccs.neu.edu/home/shivers/papers/loop.pdf">"The Anatomy of a Loop - A story of scope and control"</a> (PDF). Georgia Institute of Technology. Retrieved 2012-09-03.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFLambda_the_Ultimate" class="citation web cs1">Lambda the Ultimate. <a rel="nofollow" class="external text" href="http://lambda-the-ultimate.org/node/1014">"The Anatomy of a Loop"</a>. Lambda the Ultimate. Retrieved 2012-09-03.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.python.org/library/sys.html">"27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation"</a>. Docs.python.org. Retrieved 2012-09-03.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFKrauss2014" class="citation magazine cs1">Krauss, Kirk J. (2014). <a rel="nofollow" class="external text" href="http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-empirical-way-to-t/240169123">"Matching Wildcards: An Empirical Way to Tame an Algorithm"</a>. <a href="Dr._Dobb's_Journal" title="Dr. Dobb's Journal">Dr. Dobb's Journal</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFMueller2012" class="citation magazine cs1">Mueller, Oliver (2012). <a rel="nofollow" class="external text" href="http://www.drdobbs.com/security/anatomy-of-a-stack-smashing-attack-and-h/240001832">"Anatomy of a Stack Smashing Attack and How GCC Prevents It"</a>. <a href="Dr._Dobb's_Journal" title="Dr. Dobb's Journal">Dr. Dobb's Journal</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://msdn.microsoft.com/en-us/library/system.stackoverflowexception(v=vs.110).aspx">"StackOverflowException Class"</a>. .NET Framework Class Library. <a href="Microsoft_Developer_Network" title="Microsoft Developer Network">Microsoft Developer Network</a>. 2018.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.techiedelight.com/depth-first-search/">"Depth First Search (DFS): Iterative and Recursive Implementation"</a>. Techie Delight. 2018.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFMitrovic" class="citation web cs1">Mitrovic, Ivan. <a rel="nofollow" class="external text" href="https://www.refactoring.com/catalog/replaceRecursionWithIteration.html">"Replace Recursion with Iteration"</a>. <a href="ThoughtWorks" class="mw-redirect" title="ThoughtWorks">ThoughtWorks</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFLa2015" class="citation web cs1">La, Woong Gyu (2015). <a rel="nofollow" class="external text" href="https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and">"How to replace recursive functions using stack and while-loop to avoid the stack-overflow"</a>. CodeProject.</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFMoertel2013" class="citation web cs1">Moertel, Tom (2013). <a rel="nofollow" class="external text" href="http://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html">"Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick"</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFSalz1991" class="citation web cs1">Salz, Rich (1991). <a rel="nofollow" class="external text" href="https://github.com/trevor/transmission/blob/master/libtransmission/wildmat.c">"wildmat.c"</a>. <a href="GitHub" title="GitHub">GitHub</a>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFKrauss2008" class="citation magazine cs1">Krauss, Kirk J. (2008). <a rel="nofollow" class="external text" href="http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888">"Matching Wildcards: An Algorithm"</a>. <a href="Dr._Dobb's_Journal" title="Dr. Dobb's Journal">Dr. Dobb's Journal</a>.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFKrauss2018" class="citation web cs1">Krauss, Kirk J. (2018). <a rel="nofollow" class="external text" href="http://www.developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html">"Matching Wildcards: An Improved Algorithm for Big Data"</a>. Develop for Performance.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <a href="#CITEREFGrahamKnuthPatashnik1990">Graham, Knuth & Patashnik 1990</a>, §1.1: The Tower of Hanoi

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <a href="#CITEREFEpp1995">Epp 1995</a>, pp. 427–430: The Tower of Hanoi

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <a href="#CITEREFEpp1995">Epp 1995</a>, pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <a href="#CITEREFWirth1976">Wirth 1976</a>, p. 127

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFRussellNorvig2021" class="citation book cs1"><a href="Stuart_J._Russell" title="Stuart J. Russell">Russell, Stuart J.</a>; <a href="Peter_Norvig" title="Peter Norvig">Norvig, Peter.</a> (2021). <a href="Artificial_Intelligence%3A_A_Modern_Approach" title="Artificial Intelligence: A Modern Approach">Artificial Intelligence: A Modern Approach §9.3, §9.4</a> (4th ed.). Hoboken: Pearson. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0134610993</bdi>. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/20190474">20190474</a>.</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://runestone.academy/ns/books/published/thinkcpp/Chapter4/InfiniteRecursion.html">"4.8. Infinite Recursion"</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFBarron1968" class="citation book cs1 cs1-prop-location-test"><a href="David_W._Barron" title="David W. Barron">Barron, David William</a> (1968) [1967]. Written at Cambridge, UK. <a href="Stanley_Gill" title="Stanley Gill">Gill, Stanley</a> (ed.). Recursive techniques in programming. Macdonald Computer Monographs (1 ed.). London, UK: <a href="Macdonald_%26_Co._(Publishers)_Ltd." class="mw-redirect" title="Macdonald & Co. (Publishers) Ltd.">Macdonald & Co. (Publishers) Ltd.</a> <a href="SBN_(identifier)" class="mw-redirect" title="SBN (identifier)">SBN</a> <bdi>356-02201-3</bdi>.</cite> (viii+64 pages)</li>

<li><cite id="CITEREFFelleisenFindlerFlattKrishnamurthi2001" class="citation book cs1">Felleisen, Matthias; Findler, Robert B.; Flatt, Matthew; Krishnamurthi, Shriram (2001). <a rel="nofollow" class="external text" href="http://www.htdp.org/2003-09-26/Book/">How To Design Programs: An Introduction to Computing and Programming</a>. <a href="MIT_Press" title="MIT Press">MIT Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0262062186</bdi>.</cite></li>

<li><cite id="CITEREFRubio-Sanchez2017" class="citation book cs1">Rubio-Sanchez, Manuel (2017). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=9pY4DwAAQBAJ&pg=PA1">Introduction to Recursive Programming</a>. <a href="CRC_Press" title="CRC Press">CRC Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-351-64717-5</bdi>.</cite></li>

<li><cite id="CITEREFPevac2016" class="citation book cs1">Pevac, Irena (2016). Practicing Recursion in Java. CreateSpace Independent. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5327-1227-2</bdi>.</cite></li>

<li><cite id="CITEREFRoberts2005" class="citation book cs1">Roberts, Eric (2005). <a rel="nofollow" class="external text" href="https://archive.org/details/thinkingrecursiv00robe_0">Thinking Recursively with Java</a>. <a href="Wiley_(publisher)" title="Wiley (publisher)">Wiley</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-47170146-0</bdi>.</cite></li>

<li><cite id="CITEREFRohl1984" class="citation book cs1">Rohl, Jeffrey S. (1984). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=yCk2mWy9inMC">Recursion Via Pascal</a>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-26934-6</bdi>.</cite></li>

<li><cite id="CITEREFHelmanVeroff" class="citation book cs1">Helman, Paul; Veroff, Robert. <a href="Walls_and_Mirrors" title="Walls and Mirrors">Walls and Mirrors</a>.</cite></li>

<li><cite id="CITEREFAbelsonSussmanSussman1996" class="citation book cs1"><a href="Harold_Abelson" class="mw-redirect" title="Harold Abelson">Abelson, Harold</a>; <a href="Gerald_Jay_Sussman" title="Gerald Jay Sussman">Sussman, Gerald Jay</a>; Sussman, Julie (1996). <a href="Structure_and_Interpretation_of_Computer_Programs" title="Structure and Interpretation of Computer Programs">Structure and Interpretation of Computer Programs</a> (2nd ed.). <a href="MIT_Press" title="MIT Press">MIT Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-51087-1</bdi>.</cite></li>

<li><cite id="CITEREFDijkstra1960" class="citation journal cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> (1960). "Recursive Programming". Numerische Mathematik. 2 (1): 312–318. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01386232">10.1007/BF01386232</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:127891023">127891023</a>.</cite></li></ul>

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Programming_paradigms_(Comparison_by_language)368" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Programming_paradigms_(Comparison_by_language)368" style="font-size:114%;margin:0 4em"><a href="Programming_paradigm" title="Programming paradigm">Programming paradigms</a> (<a href="Comparison_of_multi-paradigm_programming_languages" title="Comparison of multi-paradigm programming languages">Comparison by language</a>)</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Imperative_programming" title="Imperative programming">Imperative</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Structured_programming" title="Structured programming">Structured</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Jackson_structured_programming" title="Jackson structured programming">Jackson structures</a></li>

<li><a href="Block_(programming)" title="Block (programming)">Block-structured</a></li>

<li><a href="Modular_programming" title="Modular programming">Modular</a></li>

<li><a href="Non-structured_programming" title="Non-structured programming">Non-structured</a></li>

<li><a href="Procedural_programming" title="Procedural programming">Procedural</a></li>

<li><a href="Programming_in_the_large_and_programming_in_the_small" title="Programming in the large and programming in the small">Programming in the large and in the small</a></li>

<li><a href="Design_by_contract" title="Design by contract">Design by contract</a></li>

<li><a href="Invariant-based_programming" title="Invariant-based programming">Invariant-based</a></li>

<li><a href="Nested_function" title="Nested function">Nested function</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Object-oriented_programming" title="Object-oriented programming">Object-oriented</a> (<a href="Comparison_of_programming_languages_(object-oriented_programming)" title="Comparison of programming languages (object-oriented programming)">comparison</a>, <a href="List_of_object-oriented_programming_languages" title="List of object-oriented programming languages">list</a>)</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Class-based_programming" title="Class-based programming">Class-based</a>, <a href="Prototype-based_programming" title="Prototype-based programming">Prototype-based</a>, <a href="Object-based_language" title="Object-based language">Object-based</a></li>

<li><a href="Agent-oriented_programming" title="Agent-oriented programming">Agent</a></li>

<li><a href="Immutable_object" title="Immutable object">Immutable object</a></li>

<li><a href="Persistent_programming_language" title="Persistent programming language">Persistent</a></li>

<li><a href="Uniform_function_call_syntax" title="Uniform function call syntax">Uniform function call syntax</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Declarative_programming" title="Declarative programming">Declarative</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Functional_programming" title="Functional programming">Functional</a> (<a href="Comparison_of_functional_programming_languages" title="Comparison of functional programming languages">comparison</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul>

<li><a href="Anonymous_function" title="Anonymous function">Anonymous function</a> (<a href="Partial_application" title="Partial application">Partial application</a>)</li>

<li><a href="Higher-order_programming" title="Higher-order programming">Higher-order</a></li>

<li><a href="Purely_functional_programming" title="Purely functional programming">Purely functional</a></li>

<li><a href="Total_functional_programming" title="Total functional programming">Total</a></li>

<li><a href="Strict_programming_language" title="Strict programming language">Strict</a></li>

<li><a href="Generalized_algebraic_data_type" title="Generalized algebraic data type">GADTs</a></li>

<li><a href="Dependent_type" title="Dependent type">Dependent types</a></li>

<li><a href="Functional_logic_programming" title="Functional logic programming">Functional logic</a></li>

<li><a href="Tacit_programming" title="Tacit programming">Point-free style</a></li>

<li><a href="Expression-oriented_programming_language" title="Expression-oriented programming language">Expression-oriented</a></li>

<li><a href="Applicative_programming_language" title="Applicative programming language">Applicative</a>, <a href="Concatenative_programming_language" title="Concatenative programming language">Concatenative</a></li>

<li><a href="Function-level_programming" title="Function-level programming">Function-level</a>, <a href="Value-level_programming" title="Value-level programming">Value-level</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Dataflow_programming" title="Dataflow programming">Dataflow</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Flow-based_programming" title="Flow-based programming">Flow-based</a></li>

<li><a href="Reactive_programming" title="Reactive programming">Reactive</a> (<a href="Functional_reactive_programming" title="Functional reactive programming">Functional reactive</a>)</li>

<li><a href="Signal_programming" class="mw-redirect" title="Signal programming">Signals</a></li>

<li><a href="Stream_processing" title="Stream processing">Streams</a></li>

<li><a href="Synchronous_programming_language" title="Synchronous programming language">Synchronous</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic_programming" title="Logic programming">Logic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abductive_logic_programming" title="Abductive logic programming">Abductive logic</a></li>

<li><a href="Answer_set_programming" title="Answer set programming">Answer set</a></li>

<li><a href="Constraint_programming" title="Constraint programming">Constraint</a> (<a href="Constraint_logic_programming" title="Constraint logic programming">Constraint logic</a>)</li>

<li><a href="Inductive_logic_programming" title="Inductive logic programming">Inductive logic</a></li>

<li><a href="Nondeterministic_programming" title="Nondeterministic programming">Nondeterministic</a></li>

<li><a href="Ontology_language" title="Ontology language">Ontology</a></li>

<li><a href="Probabilistic_logic_programming" title="Probabilistic logic programming">Probabilistic logic</a></li>

<li><a href="Query_language" title="Query language">Query</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Domain-specific_language" title="Domain-specific language">DSL</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algebraic_modeling_language" title="Algebraic modeling language">Algebraic modeling</a></li>

<li><a href="Array_programming" title="Array programming">Array</a></li>

<li><a href="Automata-based_programming" title="Automata-based programming">Automata-based</a> (<a href="Action_language" title="Action language">Action</a>)</li>

<li><a href="Command_language" title="Command language">Command</a> (<a href="Spacecraft_command_language" title="Spacecraft command language">Spacecraft</a>)</li>

<li><a href="Differentiable_programming" title="Differentiable programming">Differentiable</a></li>

<li><a href="Grammar-oriented_programming" title="Grammar-oriented programming">Grammar-oriented</a></li>

<li><a href="Interface_description_language" title="Interface description language">Interface description</a></li>

<li><a href="Language-oriented_programming" title="Language-oriented programming">Language-oriented</a></li>

<li><a href="List_comprehension" title="List comprehension">List comprehension</a></li>

<li><a href="Modeling_language" title="Modeling language">Modeling</a></li>

<li><a href="Natural-language_programming" class="mw-redirect" title="Natural-language programming">Natural language</a></li>

<li><a href="Non-English-based_programming_languages" title="Non-English-based programming languages">Non-English-based</a></li>

<li><a href="Page_description_language" title="Page description language">Page description</a></li>

<li><a href="Pipeline_(software)" title="Pipeline (software)">Pipes</a> and <a href="Filter_(software)" title="Filter (software)">filters</a></li>

<li><a href="Probabilistic_programming" title="Probabilistic programming">Probabilistic</a></li>

<li><a href="Quantum_programming" title="Quantum programming">Quantum</a></li>

<li><a href="Scientific_programming_language" title="Scientific programming language">Scientific</a></li>

<li><a href="Scripting_language" title="Scripting language">Scripting</a></li>

<li><a href="Set_theoretic_programming" title="Set theoretic programming">Set-theoretic</a></li>

<li><a href="Simulation_language" title="Simulation language">Simulation</a></li>

<li><a href="Stack-oriented_programming" title="Stack-oriented programming">Stack-based</a></li>

<li><a href="System_programming_language" title="System programming language">System</a></li>

<li><a href="Tactile_programming_language" title="Tactile programming language">Tactile</a></li>

<li><a href="Template_processor" title="Template processor">Templating</a></li>

<li><a href="Transformation_language" title="Transformation language">Transformation</a> (<a href="Graph_rewriting" title="Graph rewriting">Graph rewriting</a>, <a href="Production_system_(computer_science)" title="Production system (computer science)">Production</a>, <a href="Pattern_matching" title="Pattern matching">Pattern</a>)</li>

<li><a href="Visual_programming_language" title="Visual programming language">Visual</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Concurrent_computing" title="Concurrent computing">Concurrent</a>, <a href="Distributed_computing" title="Distributed computing">distributed</a>, <a href="Parallel_computing" title="Parallel computing">parallel</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Actor_model" title="Actor model">Actor-based</a></li>

<li><a href="Automatic_mutual_exclusion" title="Automatic mutual exclusion">Automatic mutual exclusion</a></li>

<li><a href="Choreographic_programming" title="Choreographic programming">Choreographic programming</a></li>

<li><a href="Concurrent_logic_programming" title="Concurrent logic programming">Concurrent logic</a> (<a href="Concurrent_constraint_logic_programming" title="Concurrent constraint logic programming">Concurrent constraint logic</a>)</li>

<li><a href="Concurrent_object-oriented_programming" title="Concurrent object-oriented programming">Concurrent OO</a></li>

<li><a href="Macroprogramming" title="Macroprogramming">Macroprogramming</a></li>

<li><a href="Multitier_programming" title="Multitier programming">Multitier programming</a></li>

<li><a href="Organic_computing" title="Organic computing">Organic computing</a></li>

<li><a href="Parallel_programming_model" title="Parallel programming model">Parallel programming models</a></li>

<li><a href="Partitioned_global_address_space" title="Partitioned global address space">Partitioned global address space</a></li>

<li><a href="Process-oriented_programming" title="Process-oriented programming">Process-oriented</a></li>

<li><a href="Relativistic_programming" title="Relativistic programming">Relativistic programming</a></li>

<li><a href="Service-oriented_programming" title="Service-oriented programming">Service-oriented</a></li>

<li><a href="Structured_concurrency" title="Structured concurrency">Structured concurrency</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Metaprogramming" title="Metaprogramming">Metaprogramming</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Attribute-oriented_programming" title="Attribute-oriented programming">Attribute-oriented</a></li>

<li><a href="Automatic_programming" title="Automatic programming">Automatic</a> (<a href="Inductive_programming" title="Inductive programming">Inductive</a>)</li>

<li><a href="Dynamic_programming_language" title="Dynamic programming language">Dynamic</a></li>

<li><a href="Extensible_programming" title="Extensible programming">Extensible</a></li>

<li><a href="Generic_programming" title="Generic programming">Generic</a></li>

<li><a href="Homoiconicity" title="Homoiconicity">Homoiconicity</a></li>

<li><a href="Interactive_programming" title="Interactive programming">Interactive</a></li>

<li><a href="Macro_(computer_science)" title="Macro (computer science)">Macro</a> (<a href="Hygienic_macro" title="Hygienic macro">Hygienic</a>)</li>

<li><a href="Metalinguistic_abstraction" title="Metalinguistic abstraction">Metalinguistic abstraction</a></li>

<li><a href="Multi-stage_programming" title="Multi-stage programming">Multi-stage</a></li>

<li><a href="Program_synthesis" title="Program synthesis">Program synthesis</a> (<a href="Bayesian_program_synthesis" title="Bayesian program synthesis">Bayesian</a>, <a href="Inferential_programming" title="Inferential programming">Inferential</a>, <a href="Programming_by_demonstration" title="Programming by demonstration">by demonstration</a>, <a href="Programming_by_example" title="Programming by example">by example</a>)</li>

<li><a href="Reflective_programming" title="Reflective programming">Reflective</a></li>

<li><a href="Self-modifying_code" title="Self-modifying code">Self-modifying code</a></li>

<li><a href="Symbolic_programming" title="Symbolic programming">Symbolic</a></li>

<li><a href="Template_metaprogramming" title="Template metaprogramming">Template</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Separation_of_concerns" title="Separation of concerns">Separation of concerns</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Aspect-oriented_programming" title="Aspect-oriented programming">Aspects</a></li>

<li><a href="Component-based_software_engineering" title="Component-based software engineering">Components</a></li>

<li><a href="Data-driven_programming" title="Data-driven programming">Data-driven</a></li>

<li><a href="Data-oriented_design" title="Data-oriented design">Data-oriented</a></li>

<li><a href="Event-driven_programming" title="Event-driven programming">Event-driven</a></li>

<li><a href="Feature-oriented_programming" title="Feature-oriented programming">Features</a></li>

<li><a href="Literate_programming" title="Literate programming">Literate</a></li>

<li><a href="Role-oriented_programming" title="Role-oriented programming">Roles</a></li>

<li><a href="Subject-oriented_programming" title="Subject-oriented programming">Subjects</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Data_structures_and_algorithms145" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Data_structures_and_algorithms145" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a> and <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data structures</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick tree</a></li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms and <a href="Algorithmic_paradigm" title="Algorithmic paradigm">algorithmic paradigms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Backtracking" title="Backtracking">Backtracking</a></li>

<li><a href="Binary_search" title="Binary search">Binary search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Brute-force_search" title="Brute-force search">Brute-force search</a></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a></li>

<li><a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">Divide and conquer</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Graph_traversal" title="Graph traversal">Graph traversal</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy</a></li>

<li><a href="Hash_function" title="Hash function">Hash function</a></li>

<li><a href="Minimax" title="Minimax">Minimax</a></li>

<li><a href="Online_algorithm" title="Online algorithm">Online</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized</a></li>

<li><a href="Root-finding_algorithm" title="Root-finding algorithm">Root-finding</a></li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting</a></li>

<li><a href="Streaming_algorithm" title="Streaming algorithm">Streaming</a></li>

<li><a href="Sweep_line_algorithm" title="Sweep line algorithm">Sweep line</a></li>

<li><a href="String-searching_algorithm" title="String-searching algorithm">String-searching</a></li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li>

<li><a href="List_of_algorithms" title="List of algorithms">List of algorithms</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-20" href="https://en.wikipedia.org/wiki/?title=Recursion_(computer_science)&oldid=1301600240">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>